package ai;

import java.util.ArrayList;
import java.util.List;

public class AIGraph<V> extends WeightedGraph<V> {

	List<Integer> nodesToVisit = new ArrayList<Integer>();
	List<Integer> visitedNodes = new ArrayList<Integer>();
	
	
	public AIGraph(List<WeightedEdge> edges, List<V> vertices) {
		super(edges, vertices);
	}
	
	public String AIdfs(int startCity, int endCity) {
		// Clear lists to prepare for path.
		nodesToVisit.clear();
		visitedNodes.clear();
		StringBuilder results = new StringBuilder();
		// turn found to true if goal is found
		boolean found = false;
		// form one-element queue consisting of a zero-length path
		// that contains only the root node
		nodesToVisit.add(startCity);
		// make list to store neighbors		
		List<Integer> neighbors;
		// until the first path in the queue terminates at the goal node
		// or the queue is empty,		
		while (!nodesToVisit.isEmpty() || found == true) {
			// if goal is the city at the head of the list, break from loop.
			if (nodesToVisit.get(0) == endCity) {
				results.append("* " + getVertex(endCity) + " *");
				found = true;
				break;
			}
			// find all neighbors of current node (head of path) &
			// remove the first node from the path
			int currentNode = nodesToVisit.remove(0);
			results.append(getVertex(currentNode) + "(");
			neighbors = getNeighbors(currentNode);			
			// add currentNode to list vistedNodes
			visitedNodes.add(currentNode);
			// create a new path by extending the first path to all neighbors of the terminal,
			// reject all new paths with loops (loop through neighbors, add new neighbors to
			// front of the queue.
			int lastNeighbor = neighbors.size() - 1;
			for (int i = lastNeighbor; i >= 0; i--) {
				results.append(getVertex(neighbors.get(i)) + ", ");	
				if (!visitedNodes.contains(neighbors.get(i))) {
					nodesToVisit.add(0, neighbors.get(i));
				}
			}
			// insert code here to return correct results string
			results.deleteCharAt(results.length() - 1);
			results.deleteCharAt(results.length() - 1);
			results.append(")\n");
		}
		return results.toString();
	}
	
	public String AIdfs(V startCity, V endCity) {
		String results = AIdfs(getIndex(startCity), getIndex(endCity));
		return results;
	}
	
	public String AIbfs(int startCity, int endCity) {
		// Clear lists to prepare for path.
		nodesToVisit.clear();
		visitedNodes.clear();
		StringBuilder results = new StringBuilder();
		// turn found to true if goal is found
		boolean found = false;
		// form one-element queue consisting of a zero-length path
		// that contains only the root node
		nodesToVisit.add(startCity);
		// make list to store neighbors		
		List<Integer> neighbors;
		// until the first path in the queue terminates at the goal node
		// or the queue is empty,		
		while (!nodesToVisit.isEmpty() || found == true) {
			// if goal is the city at the head of the list, break from loop.
			if (nodesToVisit.get(0) == endCity) {
				results.append("* " + getVertex(endCity) + " *");
				found = true;
				break;
			}
			// find all neighbors of current node (head of path) &
			// remove the first node from the path
			int currentNode = nodesToVisit.remove(0);
			results.append(getVertex(currentNode) + "(");
			neighbors = getNeighbors(currentNode);			
			// add currentNode to list vistedNodes
			visitedNodes.add(currentNode);
			// create a new path by extending the first path to all neighbors of the terminal,
			// reject all new paths with loops (loop through neighbors, add new neighbors to
			// back of the queue.
			int lastNeighbor = neighbors.size() - 1;
			for (int i = lastNeighbor; i >= 0; i--) {
				results.append(getVertex(neighbors.get(i)) + ", ");	
				if (!visitedNodes.contains(neighbors.get(i))) {
					nodesToVisit.add(neighbors.get(i));
				}
			}
			// insert code here to return correct results string
			results.deleteCharAt(results.length() - 1);
			results.deleteCharAt(results.length() - 1);
			results.append(")\n");
		}
		return results.toString();
	}
	
	public String AIbfs(V startCity, V endCity) {
		String results = AIbfs(getIndex(startCity), getIndex(endCity));
		return results;
	}
	
	public String AIastar(int startCity, int endCity) {
		return null;
	}
	
	public String AIastar(V startCity, V endCity) {
		String results = AIastar(getIndex(startCity), getIndex(endCity));
		return results;
	}
	
	
}